import java.util.Arrays;

/**
 * @ClassName KP11_binarySearch
 * @Description: TODO
 * @Author: JCC
 * @CreateTime: 2023/10/9 9:18
 */
public class KP11_binarySearch {

    /**
     * 二分查找算法
     *
     * @param sortedArray
     * @param num
     * @return
     */
    public static int binarySearch(int[] sortedArray, int num) {
        if (sortedArray == null || sortedArray.length == 0) {
            return -1;
        }
        int L = 0;
        int R = sortedArray.length - 1;
        while (L <= R) {
            int mid = (L + R) / 2;
            if (sortedArray[mid] == num) {
                return mid;
            } else if (sortedArray[mid] > num) {
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return -1;
    }

    /**
     * 生成任意规模的抽样测试数组
     *
     * @param maxLen
     * @param maxValue
     * @return
     */
    public static int[] randomArray(int maxLen, int maxValue) {
        int[] rands = new int[(int) (Math.random() * (maxLen + 1))];
        for (int i = 0; i < rands.length; i++) {
            rands[i] = (int) (Math.random() * (maxValue + 1) - Math.random() * maxValue);
        }
        return rands;
    }

    /**
     * 检查二分查找函数返回下标与实际数值在数组所在下标是否一致
     */
    public static boolean checkFindNumExist(int[] array, int index, int num) {
        if (index == -1) return false;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == num && i == index) return true;
        }
        return false;
    }

    /**
     * 生成测试查找函数
     */
    public static void testFind() {
        int maxLen = 10;
        int maxValue = 1000;
        int maxtimes = 100000;
        for (int i = 0; i < maxtimes; i++) {
            int[] rands = randomArray(maxLen, maxValue);
            Arrays.sort(rands);

            if (rands == null || rands.length == 0) {
                System.out.println("数组为null或为空");
                continue;
            }
            // 为了更好的测试生成的随机数能在数组找到
            //int randNum = rands[(int) (Math.random() * rands.length)];
            // 随机生成的数一般查找到的概率不大
            int randNum = (int) (Math.random() * (maxValue + 1) - Math.random() * maxValue);
            int index = binarySearch(rands, randNum);
            if (checkFindNumExist(rands, index, randNum)) {
                System.out.println(Arrays.toString(rands));
                System.out.println("查找成功！数值为：" + randNum + " 下标为：" + index);
            } else {
                System.out.println("查找失败！数组为：");
                System.out.println(Arrays.toString(rands));
                System.out.println("要查找的数是：" + randNum + " 返回的下标是：" + index);
            }
        }
    }

    /**
     * 根据testFind函数的测试，针对发现的问题查看代码哪里出错
     */
    public static void testCase1() {
        int[] rands1 = {41, 296, 998, 443, 964, 350, 151, 288, 805, 430};
        int randNum1 = 350;
        int index1 = binarySearch(rands1, randNum1);
        System.out.println(index1);
        int[] rands2 = {721, 593};
        int randNum2 = 593;
        int index2 = binarySearch(rands2, randNum2);
        System.out.println(index2);
        // 检测出是因为通过对数器生成的随机数组没有排序，才出错
        // 问题解决！！！
    }


    /**
     * 生成主函数
     *
     * @param args
     */
    public static void main(String[] args) {
        // 测试查找函数
        testFind();

        //测试用例1，调试错误
        //testCase1();
    }
}
